// https://leetcode.cn/problems/search-insert-position/

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size() - 1;
        while (low + 1 < high) {
            int mid = (high - low) / 2 + low;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) low = mid;
            else high = mid;
        }
        if (nums[high] < target) return high + 1; // 注意
        if (nums[low] >= target) return low; // 注意
        return high;
    }
};